package org.usmile.algorithms.leetcode.middle;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 3. 无重复字符的最长子串
 *
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * 示例 1:
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *
 * 示例 2:
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 *
 * 示例 3:
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 *
 * 提示：
 * 0 <= s.length <= 5 * 104
 * s 由英文字母、数字、符号和空格组成
 */
public class _0003 {
}

class _0003_Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxSize = 1;
        int left = 0;
        int right = 0;
        int[] window = new int[128];
        while (right < s.length()) {
            char rightChar = s.charAt(right);
            int rightCharIndex = window[rightChar];
            left = Math.max(left, rightCharIndex);
            maxSize = Math.max(maxSize, right - left + 1);
            window[rightChar] = right + 1;
            right++;
        }

        return maxSize;
    }
}

class _0003_Solution1 {
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int left = 0;
        int right = 0;
        Set<Character> windowChars = new HashSet<>();
        int maxSize = 0;
        while (right < chars.length) {
            char currChar = chars[right];
            while (windowChars.contains(currChar)) {
                windowChars.remove(chars[left]);
                left++;
            }
            windowChars.add(currChar);
            maxSize = Math.max(maxSize, right - left + 1);
            right++;
        }

        return maxSize;
    }
}

class _0003_Solution2 {
    public int lengthOfLongestSubstring(String s) {
        int maxSize = 1;
        int left = 0;
        int right = 0;
        Map<Character, Integer> window = new HashMap<>();
        while (right < s.length()) {
            char currChar = s.charAt(right);
            left = Math.max(left, window.getOrDefault(currChar, 0));
            maxSize = Math.max(maxSize, right - left + 1);
            window.put(currChar, right + 1);
            right++;
        }

        return maxSize;
    }
}
